package a_ArrayList;


public class ArrayList<E> {//使用泛型
	
	private E[] data;//创建的“通用”数组；
	private int size;  //数组中实际元素个数；
	
	//有参数的构造方法，创建指定长度的数组；
	@SuppressWarnings("unchecked")
	public ArrayList(int capacity) {
		data=(E[])new Object[capacity];//Java历史原因导致没法直接new E[]建立数组(无法直接新建泛型数组)，只能这样创建；
		size=0;
	}
	
	//方便堆的heapify优化(O(n))（比循环add效率要高O(nlogn)）
	@SuppressWarnings("unchecked")
	public ArrayList(E[] arr){
	        data = (E[])new Object[arr.length];
	        for(int i = 0 ; i < arr.length ; i ++)
	            data[i] = arr[i];
	        size = arr.length;
    }

	
	//不指定参数值的构造方法，默认创建长度为10的数组；
	public ArrayList(){
//		data=new int[10];  这两行是我的条件反射代码。。
//		size=0;
		this(10);//this()调用本类的构造方法；类似super()调用父类构造方法；
	}
	
	//获取数组实际元素个数；
	public int getSize() {
		return size;
	}
	
	//获取数组的容量；
	public int getCapacity() {
		return data.length;
	}
	
	//判断数组是不是空的；
	public boolean isEmpty() {
		return size==0;
	}
	
	//在已有的数据中插入数据；
	public void add(int index,E e) {
		if(index<0||index>size) {
			throw new IllegalArgumentException("add failed,require index>=0 and index<size.");
		}//new IllegalArgumentException(String s);是Java.lang中已有的自定义异常，**指的是非法参数异常**，我们只需自己添加错误信息即可！
		if(size==data.length){
	        resize(2*data.length);
		}
		for(int i=size-1;i>=index;i--) {
			data[i+1]=data[i];
		}
		data[index]=e;
		size++;
	}
	
	//动态数组的实现，合理地调用可以实现自动扩大或者缩小静态数组的容量；同时缩容只复制了有效元素，也就是在remove触发缩容的时候，（size--）remove掉的元素是不再存在于缩容后的新静态数组的；
	@SuppressWarnings("unchecked")
	private void resize(int newCapacity) {
        E[] newData=(E[])new Object[newCapacity];//动态数组是基于装载对象的静态数组实现的..基本数据类型是通过其对应的包装类转换成对象来存放的，实际取出来时包装类的对象可以自动转换成基本数据类型；
        for(int i=0;i<size;i++) {
			newData[i]=data[i];
        }
        data=newData;
	}

	//特别地，在开头插入比较常用可以抽出来当个方法；
	public void addFirst(E e) {
		add(0,e);
	}
	
	//特别地，在末尾插入比较常用可以抽出来当个方法；
	public void addLast(E e) {
		add(size,e);
	}

	//在指定索引的地方设置元素；
	public void set(int index,E e) {
		/*if(index<size&&index>=0) {
			data[index]=e;
		}
		else{
			throw new IllegalArgumentException("set failed,index is Illegal.");
		}这部分是自己写的代码，其实还是不够好，下面的代码利用到了throw之后的代码不执行的原理，更简洁。*/
		//抛出异常就相当于程序运行产生了异常，（此处能通过编译的原因是这个异常是一种RuntimeException）只不过抛出异常是主动的，抛出异常的地方之后的代码将不会执行。除非是try-catch体系。向调用的上层抛出则会返回调用处，异常后的代码也不会执行。
		if(index<0||index>=size){//取等号是因为用户只能看到已有的元素，size-1个。设置元素和add方法不太一样。
			throw new IllegalArgumentException("set failed,index is Illegal.");
		}
		data[index]=e;
	}
	
	//获取指定索引的元素；
	public E get(int index) {
		return data[index];
	}
	
	//判断数组中是否存在元素e；
	public boolean contains(E e) {
		for(int i=0;i<size;i++) {
			if(data[i]==e) 
				return true;
		}
			return false;
	}
	
	//返回给定的元素e的*一个*索引；如果不存在返回-1；
	public int findOneElement(E e) {
		for(int i=0;i<size;i++) {
			if(data[i]==e) {
				return i;
			}
		}
		return -1;
	}
	
	//删除指定索引的元素，并返回删除的元素值；
	public E removeIndex(int index) {
		if(index<0||index>=size) {
			throw new IllegalArgumentException("remove failed,index is illegal");
		}
		
		E removeE=data[index];
//这一步比较关键，因为接下来需要相邻赋值，所remove掉的最后一个元素将失去原有的值，而方法的初衷是返回remove掉的值，所以提前赋值不会出现bug；比如index为最后一个元素时，return data[index]就会出现空指针异常；
		
		for(int i=index+1;i<size;i++) {
			data[i-1]=data[i];
		}
		
		size--;	
		data[size]=null;//设置成null可以直接释放内存。
//如果不写data[size]=null，data[size]中将仍然存储着之前的内容。如果这个内容是一个对象的话，这个对象的内存空间不会被垃圾回收机制自动回收。但是是基本数据类型的话是可以回收的；这些是比较高级的内容，深入Java时再深究即可；此处写了最好但不写也不影响；
		
		if(size==getCapacity()/4 && getCapacity()/2!=0) {
			resize(getCapacity()/2);
		}
		return removeE;
	}
	
	public E removeFirst() {
		return removeIndex(0);
	}
	
	public E removeLast() {
		return removeIndex(size-1);
	}
	
	//实际上是删除了指定元素的第一个索引，因为是删除操作所以即使数组中不存在e也无所谓；
	public void removeOneElement(E e) {
		int index = findOneElement(e);
		if(index!=-1)
			removeIndex(index);
	}
	
	//（自己加的）删除数组中的所有指定元素。
	public void removeElement(E e) {
		while(findOneElement(e)!=-1) {
			removeOneElement(e);			
		}
	}
	
	//实现堆(最大堆最小堆)时使用
    public void swap(int i, int j){

        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    
	//覆盖进而改写继承自Object类的toString方法；为提高效率使用StringBuilder；关于String，StringBuilder，StringBuffer的区分见360账户收藏夹/印象笔记源码总结。
		@Override
		public String toString() {
			StringBuilder result=new StringBuilder();
			result.append(String.format("Array: size:%d capacity:%d\n",size,data.length));
			//类方法String.format返回一个String类型的格式化的字符串，第一个参数是包含占位符的格式化，后几个参数是替换占位符的；
			result.append("[");
			for(int i=0;i<size;i++) {
				result.append(data[i]);
				if(i!=size-1) {
					result.append(", ");
				}
			}
			result.append("]");
			return result.toString();	
		}
		
}

//常识：严格意义，说定义一个接口，是指写一个interface。不过一般在口语业务交流上，写一个方法，可以叫给用户写了一个接口，用户可以调用。这里，用户就是指使用你的类的开发者；





